package dynamic_programming;
//https://leetcode.cn/leetbook/read/illustration-of-algorithm/5vokvr/
public class LCR_166珠宝的最高价值 {
    class Solution {
        public int jewelleryValue(int[][] frame) {
            int m = frame.length, n = frame[0].length;
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(i == 0 && j == 0) continue;
                    if(i == 0) frame[i][j] += frame[i][j - 1] ;
                    else if(j == 0) frame[i][j] += frame[i - 1][j];
                    else frame[i][j] += Math.max(frame[i][j - 1], frame[i - 1][j]);
                }
            }
            return frame[m - 1][n - 1];
        }
    }
    class Solution2 {
        public int jewelleryValue(int[][] frame) {
            int m = frame.length, n = frame[0].length;
            for(int i=1; i<m; i++)// 初始化第一列
                frame[i][0] += frame[i-1][0];
            for(int i=1; i<n; i++)// 初始化第一行
                frame[0][i] += frame[0][i-1];
            for(int i=1; i<m; i++){
                for (int j = 1; j < n; j++)
                    frame[i][j] += Math.max(frame[i-1][j],frame[i][j-1]);
            }
            return frame[m-1][n-1];
        }
    }
}
